Iverson bracket

 ( Mathematical Notation ) 

In mathematics, the Iverson bracket, named after Kenneth E. Iverson, is a notation that generalises the Kronecker delta, which is the Iverson bracket of the statement . It maps any statement to a function of the in that statement. This function is defined to take the value 1 for the values of the variables for which the statement is true, and takes the value 0 otherwise. It is generally denoted by putting the statement inside square brackets: In other words, the Iverson bracket of a statement is the indicator function of the set of values for which the statement is true.

The Iverson bracket allows using capital-sigma notation without restriction on the summation index. That is, for any property $P(k)$ of the integer $k$, one can rewrite the restricted sum $\backslash sum\_\{k\; :\; P(k)\}f(k)$ in the unrestricted form $\backslash sum\_k\; f(k)\; \backslash cdotP(k)$. With this convention, $f(k)$ does not need to be defined for the values of for which the Iverson bracket equals ; that is, a summand $f(k)\backslash textbf\{false\}$ must evaluate to 0 regardless of whether $f(k)$ is defined.

The notation was originally introduced by Kenneth E. Iverson in his programming language APL,Ronald Graham, Donald Knuth, and Oren Patashnik. Concrete Mathematics, Section 2.1: Notation. though restricted to single relational operators enclosed in parentheses, while the generalisation to arbitrary statements, notational restriction to square brackets, and applications to summation, was advocated by Donald Knuth to avoid ambiguity in parenthesized logical expressions.Donald Knuth, "Two Notes on Notation", American Mathematical Monthly, Volume 99, Number 5, May 1992, pp. 403–422. ( TeX , ).

---

Properties There is a direct correspondence between arithmetic involving Iverson brackets, logical expressions, and set operations. For instance, let A and B be sets, and let $P(k\_1,\backslash dots)$ and $Q(k\_1,\backslash dots)$ be properties of integers; then we have

$$\backslash begin\{align\}$$

                      [\,P \land Q\,] ~ &= ~ [\,P\,]\,[\,Q\,]~~; \\[1em]
                       [\,P \lor Q\,] ~ &= ~ [\,P\,] \; + \; [\,Q\,] \; - \; [\,P\,]\,[\,Q\,]~~; \\[1em]
                       [\,\neg \,P\,] ~ &= ~ 1 - [\,P\,]~~; \\[1em]
     

\,P ~ &= ~ \Bigl|\,\,P\, \; - \; \,Q\, \, \Bigr| ~~; \\1em

  [\,k \in A\,] \; + \; [\,k \in B\,] ~ &= ~ [\,k \in A \cup B\,] \; + \; [\,k \in A \cap B\,]~~; \\[1em]
                 [\,x \in A \cap B\,] ~ &= ~ [\,x \in A\,]\, [\,x \in B\,]~~; \\[1em]
      [\,\forall \,m\ : \, P(k, m)\,] ~ &= ~ \prod_m\, [\,P(k, m)\,]~~; \\[1em]
      [\,\exists \,m\ : \, P(k, m)\,] ~ &= ~ \min\Bigl\{\;1\,, \,\sum_m \,[\,P(k, m)\,]\;\Bigr\} = 1 \; -  \;\prod_m \, [\,\neg\, P(k, m)\,] ~~; \\[1em]
     

\#\Bigl\{\; m \,\Big| \, P(k, m)\;\Bigr\} ~ &= ~ \sum_m \, \,P(k,~~. \end{align}

---

Examples The notation allows moving boundary conditions of summations (or integrals) as a separate factor into the summand, freeing up space around the summation operator, but more importantly allowing it to be manipulated algebraically.

---

Double-counting rule We mechanically derive a well-known sum manipulation rule using Iverson brackets:

---

Summation interchange The well-known rule $\backslash sum\_\{j=1\}^n\; \backslash sum\_\{k=1\}^j\; f(j,k)\; =\; \backslash sum\_\{k=1\}^n\; \backslash sum\_\{j=k\}^n\; f(j,k)$ is likewise easily derived: $$\backslash begin\{align\}\; \backslash sum\_\{j=1\}^n\backslash ,\backslash sum\_\{k=1\}^j\; f(j,k)$$

 &=\sum_{j,k}f(j,k)\,[1\leq j\leq n]\,[1\leq k\leq j]
     

\\&=\sum_{j,k}f(j,k)\,1\leq \\&=\sum_{j,k}f(j,k)\,1\leq\,k\leq

\\&=\sum_{k=1}^n\,\sum_{j=k}^n f(j,k). \end{align}

---

Counting For instance, Euler's totient function that counts the number of positive integers up to n which are coprime to n can be expressed by $$\backslash varphi(n)=\backslash sum\_\{i=1\}^\{n\}\backslash gcd(i,n)=1,\backslash qquad\backslash text\{for\; \}\; n\backslash in\backslash N^+.$$

---

Simplification of special cases Another use of the Iverson bracket is to simplify equations with special cases. For example, the formula $$\backslash sum\_\{1\backslash le\; k\backslash le\; n\; \backslash atop\; \backslash gcd(k,n)=1\}\backslash !\backslash !k\; =\; \backslash frac\{1\}\{2\}n\backslash varphi(n)$$

is valid for but is off by for . To get an identity valid for all positive integers (i.e., all values for which $\backslash varphi(n)$ is defined), a correction term involving the Iverson bracket may be added: $$\backslash sum\_\{1\backslash le\; k\backslash le\; n\; \backslash atop\; \backslash gcd(k,n)=1\}\backslash !\backslash !k\; =\; \backslash frac\{1\}\{2\}n\; \backslash Big(\backslash varphi(n)+n=1\backslash Big)$$

---

Common functions Many common functions, especially those with a natural piecewise definition, may be expressed in terms of the Iverson bracket. The Kronecker delta notation is a specific case of Iverson notation when the condition is equality. That is, $$\backslash delta\_\{ij\}\; =\; i=j.$$

The indicator function of a set $A$, often denoted $\backslash mathbf\{1\}\_A(x)$, $\backslash mathbf\{I\}\_A(x)$ or $\backslash chi\_A(x)$, is an Iverson bracket with set membership as its condition: $$\backslash mathbf\{I\}\_A(x)\; =\; x\backslash in.$$

The Heaviside step function, sign function, and absolute value function are also easily expressed in this notation: $$\backslash begin\{align\}$$

    H(x) &= [x \ge 0], \\
 \sgn(x) &= [x > 0] - [x < 0],
     

\end{align}

and $$\backslash begin\{align\}$$

 |x| &= x[x > 0] - x[x < 0] \\
     &= x([x > 0] - [x < 0]) \\
     &= x \cdot \sgn(x).
     

\end{align}

The comparison functions max and min (returning the larger or smaller of two arguments) may be written as $$\backslash max(x,\; y)\; =\; xx\; +\; yx$$ and $$\backslash min(x,\; y)\; =\; xx\; +\; yx.$$

The floor and ceiling functions can be expressed as $$\backslash lfloor\; x\; \backslash rfloor\; =\; \backslash sum\_n\; n\; \backslash cdot\; n$$ and $$\backslash lceil\; x\; \backslash rceil\; =\; \backslash sum\_n\; n\; \backslash cdot\; n,$$ where the index $n$ of summation is understood to range over all the integers.

The ramp function can be expressed $$R(x)\; =\; x\; \backslash cdot\; x.$$

The trichotomy of the reals is equivalent to the following identity: $$a\; +\; a\; +\; a\; =\; 1.$$

The Möbius function has the property (and can be defined by recurrence asRonald Graham, Donald Knuth, and Oren Patashnik. Concrete Mathematics, Section 4.9: Phi and Mu.) $$\backslash sum\_\{d|n\}\; \backslash mu(d)\; \backslash \; =\backslash \; n=1.$$

---

Formulation in terms of usual functions In the 1830s, Guglielmo dalla Sommaja used the expression $0^\{0^x\}$ to represent what now would be written $x$; he also used variants, such as $\backslash left(1\; -\; 0^\{0^\{-x\}\}\backslash right)\; \backslash left(1\; -\; 0^\{0^\{x-a\}\}\backslash right)$ for $0$. Following one common convention (that $0^0=1$), those quantities are equal where defined: $0^\{0^x\}$ is 1 if , is 0 if , and is undefined otherwise.

---

Notational variations

In addition to the now-standard square brackets and the original parentheses blackboard bold brackets have also been used, e.g. as well as other unusual forms of bracketing marks available in the publisher's typeface, accompanied by a marginal note.

---

See also

• Boolean function
• Type conversion in computer programming: many languages allow numeric or pointer quantities to be used as boolean quantities
• Indicator function

Categories: Mathematical Notation

Post Comment